package com.tgy.leetcode;

import java.util.PriorityQueue;
import java.util.Queue;
import java.util.TreeMap;

/**
 * @Author: tgy
 * @Date: 2021/2/21 下午10:31
 */
public class _1438_绝对差不超过限制的最长连续子数组_TreeMap {

    public static int longestSubarray(int[] nums, int limit) {
        int left = 0, right = 0;
        int max_len = 0;
        TreeMap<Integer,Integer> treeMap = new TreeMap<>();

        while (right < nums.length) {

            treeMap.put(nums[right], treeMap.getOrDefault(nums[right],0) + 1);

            while (treeMap.lastKey() - treeMap.firstKey() > limit) {

                int count = treeMap.get(nums[left]) - 1;

                if (count == 0) {

                    treeMap.remove(nums[left]);
                }else {
                    treeMap.put(nums[left],count);
                }

                left++;
            }

            max_len = Math.max(max_len,right - left + 1);
            right++;
        }

        return max_len;
    }

    public static int longestSubarray01(int[] nums, int limit) {

        int left = 0, right = 0;
        int max_len = 0;
        TreeMap<Integer,Integer> treeMap = new TreeMap<>();

        treeMap.put(nums[left],1);

        while (right < nums.length) {

            if (treeMap.lastKey() - treeMap.firstKey() > limit) {

                max_len = Math.max(max_len,right - left);
                Integer count = treeMap.get(nums[left]) - 1;

                if (count == 0) {

                    treeMap.remove(nums[left]);
                }else {
                    treeMap.put(nums[left],count);
                }

                left++;
            }else {
                right++;
                if (right < nums.length) {

                    treeMap.put(nums[right],treeMap.getOrDefault(nums[right],0) + 1);
                }
            }
        }

        max_len = Math.max(max_len,right - left);
        return max_len;
    }


    public static void main(String[] args) {

        int[] nums = {10,1,2,4,7,2};
        int k = 5;
        int result = longestSubarray(nums, k);
        System.out.println(result);

    }
}
